﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <chrono>
#include <functional>
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
    {
        //按照左端点排序
        //首先开辟一个二维数组，表示某个主持人，主持的节目的最晚结束时间
        //来了一个新元素，存到当前新主持节目开始时间大于某个主持人最晚结束时间的位置，如果没有，重新分配一个主持人
        //最坏情况，每次遍历n个主持人，n个数据为o（n^2）
        //小根堆优化，最早结束时间的主持人看看能不能主持该新活动
        //如果连最早结束时间的主持人都不能主持该节目，其他更晚结束时间的主持人更不能主持该节目
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> q;//小根堆

        for (int i = 0; i < n; ++i)//遍历元素
        {
            if (q.empty() || q.top() > startEnd[i][0])//小根堆为空 或者 最早结束时间的主持人也无法主持该活动
            {
                q.push(startEnd[i][1]);//结束时间入小根堆
            }
            else//可以主持，存的是最晚结束时间
            {
                q.pop();
                q.push(startEnd[i][1]);
            }
        }

        return q.size();//主持人的数量
    }
};

/*
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,
第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，
换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 
这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
数据范围:1≤n≤10^5，−2^32≤starti≤endi≤2^31−1复杂度要求：时间复杂度O(nlogn) ，空间复杂度O(n)

示例1
输入：
2,[[1,2],[2,3]]
返回值：
1
说明：
只需要一个主持人就能成功举办这两个活动
*/

